package com.exam.exercise;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

/**
 * @Author: xin.wang  E-mail:xin.wang1@myt11.com
 * @CreateTime: 2022/4/1 15:24
 * @Description: 三数之和
 */
public class FourthExercise {
    /**
     * 给出一个有n个元素的数组S，S中是否有元素a,b,c满足a+b+c=0？找出数组S中所有满足条件的三元组。
     * <p>
     * 示例1
     * 输入：[-10,0,10,20,-10,-40]   返回值：[[-10,-10,20],[-10,0,10]]
     * 示例2
     * 输入：[-2,0,1,1,2]   返回值：[[-2,0,2],[-2,1,1]]
     * 示例3
     * 输入：[0,0]   返回值：[]
     *
     * @param args
     */
    public static void main(String[] args) {
        int[] nums = {-10, 0, 10, 20, -10, -40};
        System.out.println(threeNumberSum(nums));
    }

    public static List<List<Integer>> threeNumberSum(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> res = new LinkedList<>();
        for (int i = 0; i < nums.length; i++) {
            if ((i > 0) && (nums[i] == nums[i - 1])) {
                continue;
            }
            int last = i + 1;//i后一位
            int end = nums.length - 1;//最后一位
            while (last < end) {
                int sum = nums[i] + nums[last] + nums[end];
                if (sum > 0) {
                    end--;//向前移
                } else if (sum < 0) {
                    last++;//向后移
                } else {
                    res.add(Arrays.asList(nums[i], nums[last], nums[end]));
                    while (last + 1 < end && nums[last] == nums[last + 1]) {
                        last++;
                    }
                    while (end - 1 > last && nums[end] == nums[end - 1]) {
                        end--;
                    }
                    last++;
                    end--;
                }
            }
        }
        return res;
    }
}
